package com.example.niuke.bytedance.array;


import java.util.HashSet;
import java.util.Set;

/**
 * 作者：莫奇311
 * 链接：https://www.nowcoder.com/discuss/461587
 * 来源：牛客网
 *
 * 算法题 -- 剑指offer 3改编
 * 1
 * 2
 * int 数组， size N, 元素范围 0～ N-1， 求存在重复的元素。
 * 要求： 时间O（N）， 空间O（1）
 * 一开始只想着求一个元素，将数组都加个1，则范围变为 1 - N，则可以变成一个链表求环的入口问题，说了半天，面试官没听太懂，让我先写，我写到一半，面试官说这是只找一个嘛，要找多个怎么办。
 * 又想了好一会，跟面试官说了另外一种思路，后面面试官提示了下，改成另外一种方案了，代码如下。

 * class FindRepeatNum{
 *     public Set<Integer> findRepeat(int[] nums){
 *         int n = nums.length;
 *         Set<Integer> res = new HashSet<>();
 *         if(n == 0) return res;
 *         for(int i = 0; i <n; i++){
 *             int idx = nums[i] % n;
 *             nums[idx] += n;
 *             if(nums[idx] / n >= 2) res.add(idx);
 *         }
 *         return res;
 *     }
 * }
 * 更新：上述代码有个问题，应该是nums[i] % n，之前写的是nums[i % n]，这个是有问题的，感谢“我非真心”小伙伴私信提醒。
 * 补充个示例：
 * 第一行是下标，第二行是数组数据，第三行是遍历一遍的数据
 * 0 1 2 3
 * 1 0 2 2
 * 4 3 8 2
 * 这里遍历到下标3的时候，下标2对应的数字变为8，对应出现两次，即可找到答案。相应的如果有多个数据，那么也是一样的逻辑
 */
class FindRepeatNum{

    public Set<Integer> findRepeat(int[] nums){
        int n = nums.length;
        Set<Integer> res = new HashSet<>();
        if(n == 0) return res;
        for(int i = 0; i <n; i++){
            int idx = nums[i] % n;
            nums[idx-1] += n;
            if(nums[idx-1] / n >= 2) res.add(idx);
        }       
        return res;       
    }

    public static void main(String[] args) {
        FindRepeatNum num=new FindRepeatNum();
        int [] nums={1,2,3,4,5,4,5,2,3,1};
        System.out.println(num.findRepeat(nums));
    }

}